package com.asia.algorithmcode.dynamicProgram;


import java.util.*;

/**
 * 140、单词拆分2
 */
public class WordBreak_2 {

    public static void main(String[] args) {
        String s = "catsanddog";
        List<String> dict = Arrays.asList("cat", "cats", "and", "sand", "dog");

        System.out.println(new WordBreak_2().wordBreak(s, dict));
    }

    // 单词拆分2
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<Integer, List<List<String>>> map = new HashMap<>();
        List<List<String>> wordBreaks = backtrack(s, s.length(), new HashSet<String>(wordDict), 0, map);
        List<String> breakList = new LinkedList<String>();
        for (List<String> wordBreak : wordBreaks) {
            breakList.add(String.join(" ", wordBreak));
        }
        return breakList;
    }

    /**
     * 回溯方法
     *
     * @param s       原字符串
     * @param length  原字符串长度
     * @param wordSet 单词字典
     * @param index   索引的起始位置
     * @param map     记忆化搜索的哈希表
     * @return 返回从源字符串的起始位置，可以用字典中的单词将原字符串切割出多少种组合
     */
    public List<List<String>> backtrack(String s, int length, Set<String> wordSet, int index, Map<Integer, List<List<String>>> map) {
        if (!map.containsKey(index)) {
            List<List<String>> resList = new LinkedList<>();
            // 从末尾到末尾，已经没有长度可以用来切分，这个时候的结果是空
            if (index == length) {
                resList.add(new LinkedList<>());
            }
            // 从index+1到length之间的字符串可以由字典组合出多少种切分方式
            for (int i = index + 1; i <= length; i++) {
                String word = s.substring(index, i);
                if (wordSet.contains(word)) {
                    List<List<String>> backtrack = backtrack(s, length, wordSet, i, map);
                    for (List<String> subList : backtrack) {
                        LinkedList<String> innerList = new LinkedList<>(subList);
                        innerList.offerFirst(word);
                        resList.add(innerList);
                    }
                }
            }
            // cache 从index起始位置的切分方法
            map.put(index, resList);
        }
        return map.get(index);
    }

}
